package com.liu.BITOperation;

import java.util.Random;

public class UniquePairNUmber {
    // 找出数组中唯一成对的数
    /*
        1-1000这1000个数放在含有1001个元素的数组中，只有唯一的一个元素值重复，
        其它均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来;
        不用辅助存储空间，能否设计一个算法实现?
     */
    public static void main(String[] args) {
        int N = 5;
        // 创建数组
        int[] arr = new int[N];
        for (int i = 0; i < arr.length - 1; i++) {
            arr[i] = i + 1;
        }
        // 最后一个数是随机数
        arr[arr.length - 1] = new Random().nextInt(N - 1) + 1;
        // 随机下标
        int index = new Random().nextInt(N);
        swap(arr,index,arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }

        int x1 = 0;
        // 先将 1 ~ 1000 的数字两两异或，得到x1
        for (int i = 1; i <= N - 1; i++) {
            x1 = x1 ^ i;
        }
        // 将 x1 与 arr数组中的每个值异或
        for (int i = 0; i < N; i++) {
            x1 = x1 ^ arr[i];
        }
        System.out.println(x1);

        System.out.println("--------------暴力破解（辅助空间）");
        int[] helper = new int[N];
        for (int i = 0; i < N; i++){
            helper[arr[i]]++;
        }
        for (int i = 0; i < N; i++) {
            if (helper[i] == 2){
                System.out.println(i);
                break;
            }
        }
    }
    public static void swap(int[] arr, int i, int j){
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] =  t;
    }
}
